import java.util.Arrays;
import java.util.stream.Stream;

public class Solution213 {
    public int[] arrSub(int[] nums,int start,int end){
        int[] newArr=new int[end-start];
        int newInd=0;
        for (int i = start; i < end; i++) {
            newArr[newInd++]=nums[i];
        }
        return newArr;
    }

    public int doRob(int[] nums){
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[1],nums[0]);
        for (int i = 2; i < nums.length; i++) {
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[nums.length-1];
    }

    public int rob(int[] nums) {
        if(nums.length<=2){
            return nums.length==0? 0:Arrays.stream(nums).max().getAsInt();
        }
        return Math.max(doRob(arrSub(nums,0,nums.length-1)),doRob(arrSub(nums,1,nums.length)));
    }

    public static void main(String[] args) {
        Solution213 s=new Solution213();
        s.rob(new int[]{1,3,1,3,100});
    }
}
